package likou.offer;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/5  19:49
 */
public class _26 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        TreeNode A = new TreeNode(1);
        A.left = new TreeNode(2);
        A.right = new TreeNode(3);
        A.left.left = new TreeNode(4);
//        A.left.right = new TreeNode(1);


        TreeNode B = new TreeNode(3);
        System.out.println(isSubStructure(A, B));
    }

    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null || A == null) {
            return false;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode temp = A;
        boolean daan = false;
        while (deque.size() != 0 || temp != null) {
            while (temp != null) {
                deque.push(temp);
                temp = temp.left;
            }
            if (deque.size() != 0) {
                temp = deque.pop();
                if (temp.val == B.val) {
                    daan = daan || getDaan(temp, B);
                }
                temp = temp.right;
            }
        }
        return daan;
    }

    public static boolean getDaan(TreeNode A, TreeNode B) {
        Deque<TreeNode> deque = new LinkedList<>();
        Deque<TreeNode> dequeB = new LinkedList<>();
        TreeNode temp = A;
        TreeNode tempB = B;
        while (dequeB.size() != 0 || tempB != null) {
            while (tempB != null) {
                if (temp == null || (temp.val != tempB.val)) {
                    return false;
                }
                dequeB.push(tempB);
                deque.push(temp);
                tempB = tempB.left;
                temp = temp.left;
            }
            if (dequeB.size() != 0) {
                tempB = dequeB.pop();
                temp = deque.pop();
                tempB = tempB.right;
                temp = temp.right;
                if ((deque.size() == 0 && dequeB.size() != 0) || (temp != null && tempB != null && temp.val != tempB.val)) {
                    return false;
                }
            }
        }
        return true;
    }

//    public static boolean isSubStructure(TreeNode A, TreeNode B) {
//        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
//    }
//
//    public static boolean recur(TreeNode A, TreeNode B) {
//        if (B == null) return true;
//        if (A == null || A.val != B.val) return false;
//        return recur(A.left, B.left) && recur(A.right, B.right);
//    }
}
